/**
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。
（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 */
var zigzagLevelOrder = function(root) {
  if(!root) return []
  const res = []
  const queue = [root]
  let index = 0
  while(queue.length) {
    const size = queue.length
    const level = []
    for(let i=0;i<size;i++) {
      const node = queue.shift()
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
      level.push(node.val)
    }
    res.push(index&1 ? level.reverse(): level)
    index++
  }
  return res
};